package com.gframework.datastructure.trie;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 这是一个基本的线程安全的单词查找树.
 * <p>
 * 本类可以识别一串字符串中的多个铭感词，能够找出他们的位置并且能够迭代处理。
 * 同时匹配模式是按照最长匹配原则进行匹配的。
 * </p>
 * <p>
 * 本类采用ReinitOnWrite技术，不同于CopyOnWrite，它的性能是更差的，以此保证安全高效的搜索效率。
 * 如果你要进行铭感词汇的修改，请使用 {@link #addAll(Collection)} 或 {@link #addAll(String[])} 方法，而不是 {@link #add(String)} 方法。
 * </p>
 * 
 * @since 1.0.0
 * @author Ghwolf
 */
public class StringTrieTree implements TrieTree,Serializable {
	private static final long serialVersionUID = 9152463061632055014L;
	
	/**
	 * 这是一个会忽略空和空字符串的hashSet集合
	 * @since 1.0.0
	 * @author Ghwolf
	 *
	 */
	private class NoEmptyHashSet extends HashSet<String> {
		private static final long serialVersionUID = -5698269307466555619L;
		@Override
		public boolean add(String e) {
			if (e == null || e.equals("")) {
				return false ;
			}
			return super.add(e);
		}
	}
	
	/**
	 * 存储所有单词的集合
	 */
	private final Set<String> codes = new NoEmptyHashSet() ;
	/**
	 * 锁对象
	 */
	private final transient ReentrantLock lock = new ReentrantLock();
	/**
	 * 根节点，根节点存储的char没有意义
	 */
	private volatile Node root = createRootNode();

	/**
	 * 节点类
	 */
	private class Node implements Serializable{
		private static final long serialVersionUID = -1388682275677459524L;
		/**
		 * 当前节点的字符
		 */
		private final char value ;
		/**
		 * 子节点数组
		 */
		private Node[] leaf ;
		/**
		 * 是否是一个单词的结尾节点
		 */
		private final boolean wordEnd ;
		
		Node(char value,boolean wordEnd) {
			this.value = value;
			this.wordEnd = wordEnd;
		}

		final int getValue() {
			return value;
		}
		/**
		 * 是否有叶子节点
		 */
		final boolean hasLeaf() {
			return this.leaf != null ;
		}
		/**
		 * 取得叶子节点，如果没有返回null
		 */
		final Node[] getLeaf() {
			return this.leaf;
		}
		
		/**
		 * 当前节点是否是一个单词的结尾
		 * @return 如果是返回true，否则返回false
		 */
		final boolean isWordEnd() {
			return this.wordEnd;
		}
		
	    /**
	     * 取得当前子节点中，第一个指定value所在位置的索引.
	     * <p>
	     * 此方法采用二分查找法进行检索
	     * </p>
	     * @param value 要查询的value值
	     * @return 返回第一次出现所在的索引位置，没有返回-1
	     */
	    int indexOfByVaue(int value) {
	    	int i = this.binarySearch(value);
	    	if (i == -1) {
	    		return -1 ;
	    	}
	    	// 筛选第一次出现的索引
	    	while(i > 0 && this.leaf[i - 1] == this.leaf[i]) {
	    		i --;
	    	}
	    	return i ;
	    }
		
	    /**
	     * 二分查找value所在元素的位置.
	     * 如果存在多个同值元素，那么此方法返回的索引具体是哪个是不确定的，这与数组总长度有关，涉及到除法计算优先到达的位置。
	     * <p>
	     * Arrays.binarySearch方法存在一些缺陷，直接调用会存在较大的复杂性。
	     * </p>
	     */
	    private int binarySearch(int value) {
	    	if (this.leaf == null || this.leaf.length == 0) return -1 ;
	    	if (value < this.leaf[0].getValue() || value > this.leaf[this.leaf.length - 1].getValue()) {
	    		return - 1;
	    	}
	    	
	    	int low = 0;
	        int high = this.leaf.length - 1;

	        while (low <= high) {
	            int mid = (low + high) >>> 1;
				int midVal = this.leaf[mid].getValue();

	            if (value > midVal)
	                low = mid + 1;
	            else if (value < midVal)
	                high = mid - 1;
	            else
	                return mid;
	        }
	    	return -1 ;
	    }
		
		/**
		 * 以当前节点为根节点，初始化所有的单词
		 * @param strs 初始化的单词集合
		 */
		void init(String[] strs) {
			if (strs == null || strs.length == 0) return ;
			Arrays.sort(strs);
			add(strs,0,0,strs.length - 1);
		}
		
		private void add(String[] strs,final int index,int start,int end) {
			List<Node> list = new ArrayList<>(end - start + 1);
			int nextStart = start ;
			boolean endWord = false;
			for (int x = start ; x <= end ; x ++) {
				String str = strs[x];
				if (index >= str.length()) {
					continue ;
				}
				endWord |= index == str.length() - 1 ;
				char c = str.charAt(index);
				
				if (x == end || strs[x + 1].charAt(index) != c) {
					Node node = new Node(c,endWord);
					list.add(node);
					node.add(strs, index + 1, nextStart, x);
					nextStart = x + 1;
					endWord = false ;
				}
				
			}
			if (!list.isEmpty()) {
				this.leaf = list.toArray(new Node[list.size()]);
			}
		}
		
	}
	
	
	/**
	 * 添加一个新的特殊词汇.
	 * <p>
	 * 不建议使用此方法进行批量添加，因为本类集合存储采用的是CopyOnWrite技术，每次只添加一条会造成极大的性能损耗。
	 * <br><strong>建议使用{@link #addAll(Collection)} 或 {@link #addAll(String[])} 方法</strong>
	 * </p>
	 * @param code 要添加的词汇，如果为null或空字符串，则不做任何事情
	 */
	public void add(String code) {
		if (code == null || code.equals("")) {
			return ;
		}
		
		this.lock.lock();
		try {
			if (this.codes.add(code)) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}
	/**
	 * 添加多个特殊词汇.
	 * @param codes 如果集合为null或空，则不做任何事情
	 */
	public void addAll(Collection<String> codes) {
		if (codes == null || codes.isEmpty()) {
			return ;
		}
		
		this.lock.lock();
		try {
			if (this.codes.addAll(codes)) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}

	/**
	 * 添加多个特殊词汇.
	 * @param codes 如果集合为null或空，则不做任何事情
	 */
	public void addAll(String[] codes) {
		if (codes == null || codes.length == 0) {
			return ;
		}
		
		this.lock.lock();
		try {
			if (Collections.addAll(this.codes, codes)) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}
	
	/**
	 * 删除一个铭感词
	 * @param code 要删除的词汇
	 */
	public void remove(String code) {
		if (code == null || code.equals("")) {
			return ;
		}
		
		this.lock.lock();
		try {
			if (this.codes.remove(code)) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}
	/**
	 * 删除多个铭感词
	 * @param codes 要删除的词汇
	 */
	public void remove(Collection<String> codes) {
		if (codes == null || codes.isEmpty()) {
			return ;
		}
		
		this.lock.lock();
		try {
			if (this.codes.removeAll(codes)) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}
	/**
	 * 删除多个铭感词
	 * @param codes 要删除的词汇
	 */
	public void remove(String[] codes) {
		if (codes == null || codes.length == 0) {
			return ;
		}
		
		this.lock.lock();
		try {
			boolean isChange = false ;
			for (int x = 0 ; x < codes.length ; x ++) {
				isChange |= this.codes.remove(codes[x]);
			}
			if (isChange) {
				this.reinitOnWrite();
			}
		} finally {
			this.lock.unlock();
		}
	}
	
	@Override
	public String each(String str, StringHandleFunction handler) {
		if (str == null) return null ;
		
		StringBuilder value = new StringBuilder(str.length());
		
		for (int x = 0 ; x < str.length() ;) {
			int y = x ;
			char c = str.charAt(y);
			Node node = this.root;
			int wordEndIndex = -1 ;
			int i ;
			while ( (i = node.indexOfByVaue(c)) != -1) {
				node = node.getLeaf()[i];
				if (node.isWordEnd()) {
					wordEndIndex = y ;
				}
				y ++;
				if (y >= str.length()) {
					break ;
				} else {
					c = str.charAt(y);
				}
			}
			if (wordEndIndex != -1) {
				String s = handler.handle(str, str.substring(x, wordEndIndex + 1), x, wordEndIndex);
				value.append(s);
				x = wordEndIndex + 1;
			} else {
				value.append(str.charAt(x));
				x ++ ;
			}
		}
		
		return value.toString();
	}

	@Override
	public boolean match(String str) {
		return this.indexOf(str) != -1;
	}

	@Override
	public int indexOf(String str) {
		return this.indexOf(str,0);
	}

	@Override
	public int indexOf(String str, int fromIndex) {
		if (str == null) return -1 ;
		
		for (int x = fromIndex ; x < str.length() ; x ++) {
			int y = x ;
			char c = str.charAt(y);
			Node node = this.root;
			int i ;
			while ( (i = node.indexOfByVaue(c)) != -1) {
				node = node.getLeaf()[i];
				if (node.isWordEnd()) {
					return x;
				}
				y ++;
				if (y >= str.length()) {
					break ;
				} else {
					c = str.charAt(y);
				}
			}
		}
		
		return -1;
	}
	
	@Override
	public String getFormatString(String title) {
		StringBuilder value = new StringBuilder(1024);
		value.append("====== " + title + " ======\n");
		if (this.root.hasLeaf()) {
			this.handleFormatString(this.root, "", value);
		}
		return value.toString();
	}
	/**
	 * 只能由 {@link #getFormatString(String)} 方法调用。
	 */
	private void handleFormatString(Node node,String prefix,StringBuilder value) {
		if (node.getLeaf() != null) {
			String nextPrefix = prefix + ".";
			for (Node n : node.getLeaf()) {
				value.append(prefix).append(Character.valueOf((char)n.getValue()));
				if (n.isWordEnd()) {
					value.append("-$");
				}
				value.append('\n');
				if (n.hasLeaf()) {
					this.handleFormatString(n, nextPrefix, value);
				}
			}
		}
	}
	
	/**
	 * 每次添加都重新初始化
	 */
	private void reinitOnWrite() {
		Node node = this.createRootNode();
		node.init(this.codes.toArray(new String[this.codes.size()]));
		this.root = node ;
	}
	
	
	/**
	 * 创建根节点对象
	 */
	private final Node createRootNode() {
		return new Node('\0',false);
	}

}
